Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики
і фундаментальних наук
Кафедра прикладної математики
Лабораторна робота № 3
Знаходження максимального потоку в транспортній мережі
Виконав: студент групи ПМ-22
Львів 2007
Умова задачі:
5.6. Знайти потік найбільшої величини для транспортної сітки:
01
12
23
15
05
06
76
57
68
78
37
34
56
48
49
89
4z
9z
7
10
15
4
10
11
17
18
21
23
19
14
15
17
10
19
19
25
Текст програми:
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
//----------------------CONSTANTS AND VARIABLES------------
const kilver=11; //kilkist vershyn
int x0=0; //pochatkova vershyna
int z=10; //kinceva vershyna
int c[kilver][kilver]={ //matrycya propusknyh spromognostey V-25
{0, 7, 0, 0, 0,10,11, 0, 0, 0, 0},
{0, 0,10, 0, 0, 4, 0, 0, 0, 0, 0},
{0, 0, 0,15, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0,14, 0, 0,19, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0,17,10,19},
{0, 0, 0, 0, 0, 0,15,18, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0,21, 0, 0},
{0, 0, 0, 0, 0, 0,17, 0,23, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0,19, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0,25},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
struct tochka { int nomer; int vidmichena; int znak; };
int pomicheni[kilver]; //masyp pomichenyh vershyn
int f[kilver][kilver]; //matrycya potokiv po rebrah
int potic; //max potik cherez meregu
tochka path[kilver]; //masyv v jakomu vidobragaetsja shljah
int pathlen; //dovgyna vybranogo shlyahu
//----------------------FUNCTION PROTOTYPES----------------
void initialization(void);
void pershyj_etap(void);
void drugyj_etap(void);
void vyvid(void);
//void findpath(void);
int min(tochka *path, int pathlen);
//----------------------MAIN-------------------------------
void main(void)
{clrscr();
initialization();
pershyj_etap();
drugyj_etap();
vyvid();
getch();}
//----------------------FUNCTION BODIES--------------------
void initialization(void)
{potic=0;
pathlen=0;
for(int i=0; i<kilver; i++)
{
for(int j; j<kilver; j++)
{f[i][j]=0;};
path[i].nomer=-1;
pomicheni[i]=-1;
}
path[0].nomer=0;}
//----------------------
void pershyj_etap(void)
{int i;
for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=0;};
int pr=1; //praporec, vidpovidae za isnuvannya shljahu
int minchyslo;
for(;pr==1;)
{
for(int u=0;u<kilver;u++){path[u].nomer=-1;};
path[0].nomer=0;
pathlen=0;
i=0;
for(;path[pathlen].nomer!=z;)//znahogennya shlyahu
{
for(int j=0;j<kilver;j++) //vybyraem nastupnu (sumignu)
{
pr=0; //shlyah ne isnue
if(c[path[pathlen].nomer][j]-f[path[pathlen].nomer][j]>0)
{//perevirka chy sumigne i chy propuskae she shos
path[pathlen+1].nomer=j;/*path[j].vidmichena=1;break;*/
pathlen++;
pr=1; //shlyah isnue
i=path[pathlen].nomer;
break;
}
}
if(pr==0){break;};
}//for i
if(pr==1)
{
minchyslo = min(path,pathlen);
potic+=minchyslo;
for(int i=0;i<pathlen;i++)
{
f[path[i].nomer][path[i+1].nomer]+=minchyslo;
}
pathlen=0;
}
}//for pr==1
}
//----------------------
int min(tochka *path, int pathlen)
{int ret=c[0][path[1].nomer]-f[0][path[1].nomer];
for(int i=1;i<pathlen+1;i++)
{
if((path[i+1].znak==1)+(path[i+1].vidmichena==0)==1)
{
if(c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer]<ret)
{ret=c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer];};
}
if(path[i+1].znak==-1)
{
if(f[path[i].nomer][path[i+1].nomer]<ret)
{ret=f[path[i+1].nomer][path[i].nomer];};
}
}
return ret;}
//----------------------
void drugyj_etap(void)
{int i;
for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=-1;};
int pr=1; //praporec, vidpovidae za isnuvannya shljahu
int minchyslo;
int br;
for(;pr==1;)
{
for(int u=0;u<kilver;u++)
{path[u].nomer=-1;path[u].vidmichena=-1;path[u].znak=0;pomicheni[u]=-1;};
path[0].nomer=0;
path[0].vidmichena=0;
pomicheni[0]=1;
pathlen=0;
i=0;
f...
